package q779_kthGrammar;

public class Solution_3 {
    /*
    本质上我们其实只需要求在过程中的“翻转”总次数，
    如果“翻转”为偶数次则原问题求解为 0，否则为 1。
    因此原问题中求“翻转”的总次数就等价于求 k−1 的二进制表示中 1 的个数
     */
    public int kthGrammar(int n, int k) {
        // return Integer.bitCount(k - 1) & 1;
        k--;
        int res = 0;
        while (k > 0) {
            k &= k - 1;
            res ^= 1;
        }
        return res;
    }
}
